//
// Created by wdq on 2022/9/9.
//
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdio>

bool stringCmp(const std::string &source, const std::string &target, int pos = 0) {
    for (int i = pos, j = 0; i < source.size() && j < target.size(); i++, j++) {
        if (target[j] != source[i]) {
            return false;
        }

    }
    return true;
}


int findIndex(const std::string &source, const std::string &target) {
    if (target.size() > source.size()) {
        return -1;
    }
    for (int i = 0; i <= int(source.size() - target.size()); i++) {
        if (stringCmp(source, target, i)) {
            return i;
        }
    }
    return -1;

}

std::vector<int> getNext(const std::string &source, int length) {
    std::vector<int> next(length);
    int i = 0;
    int j = -1;
    next[0] = -1;
    while (i < int(source.size())) {
        if (j == -1 || source[i] == source[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    return next;

}

int findIndexByKMP(const std::string &source, const std::string &target) {
    if (target.size() > source.size()) {
        return -1;
    }
    std::vector<int> next = getNext(source, int(source.size()));
    int i = 0;
    int j = 0;
    while (i < int(source.size()) && j < int(target.size())) {
        if (j == -1 || source[i] == target[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == int(target.size())) {
        return i - j;
    }
    return -1;

}

std::vector<int> getSkipTableSunday(const std::string &target) {
    //ascii有128个
    std::vector<int> skipTable(128);
    for (auto &i: skipTable) {
        //如果一个字符没有在模式串中出现需要移动模式串的长度加1的长度
        i = int(target.size()) + 1;
    }
    for (int i = 0; i < target.size(); i++) {
        //如果出现过，就要移动串的长度-最后出现的位置的长度
        skipTable[target[i]] = int(target.size()) - i;
    }
    return skipTable;
}


int findIndexBySunday(const std::string &source, const std::string &target) {
    if (target.size() > source.size()) {
        return -1;
    }
    std::vector<int> skipTable = getSkipTableSunday(target);
    int n = int(source.size());
    int m = int(target.size());
    int i = 0;
    int sub = n - m;
    while (i <= sub) {
        if (stringCmp(source, target, i)) {
            return i;
        }
        i += skipTable[source[i + m]];
    }
    return -1;

}


std::vector<int> getSkipTableHorsPool(const std::string &target) {
    //ascii有128个
    std::vector<int> skipTable(128);
    for (auto &i: skipTable) {
        //如果一个字符没有在模式串中出现需要移动模式串的长度
        i = int(target.size());
    }
    for (int i = 0; i < target.size() - 1; i++) {
        //如果出现过，就要移动串的长度-最后出现的位置的长度-1
        skipTable[target[i]] = int(target.size()) - i - 1;
    }
    return skipTable;
}

int findIndexByHorsPool(const std::string &source, const std::string &target) {
    if (target.size() > source.size()) {
        return -1;
    }
    std::vector<int> skipTable = getSkipTableHorsPool(target);
    int n = int(source.size());
    int m = int(target.size());
    for (int i = 0; i <= n - m;) {
        if (stringCmp(source, target, i)) {
            return i;
        }
        i += skipTable[source[i + m - 1]];
    }
    return -1;


}

int main() {
    std::string a = "abcddderffsssawwdqqza";
    std::string b = "wdq";
    time_t begin, end;
    float cost;
    int pos;

    time(&begin);
    for (int i = 0; i <= 10000000; i++) {
        pos = findIndex(a, b);
    }
    time(&end);
    cost = float(end - begin);
    printf("BF: the position is %d, the cost is %.2fs\n", pos, cost);

    time(&begin);
    for (int i = 0; i <= 10000000; i++) {
        pos = findIndexByKMP(a, b);
    }
    time(&end);
    cost = float(end - begin);
    printf("KMP: the position is %d, the cost is %.2fs\n", pos, cost);

    time(&begin);
    for (int i = 0; i <= 10000000; i++) {
        pos = findIndexBySunday(a, b);
    }
    time(&end);
    cost = float(end - begin);
    printf("Sunday: the position is %d, the cost is %.2fs\n", pos, cost);

    time(&begin);
    for (int i = 0; i <= 10000000; i++) {
        pos = findIndexByHorsPool(a, b);
    }
    time(&end);
    cost = float(end - begin);
    printf("HorsPool: the position is %d, the cost is %.2fs\n", pos, cost);

    time(&begin);
    for (int i = 0; i <= 10000000; i++) {
        pos = int(a.find(b));
    }
    time(&end);
    cost = float(end - begin);
    printf("string.find(): the position is %d, the cost is %.2fs\n", pos, cost);
    return 0;
}